#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int longestWPI(vector<int>& hours) {
        vector<int>nums(hours.size()+1);
        nums[0] = 0;
        for (int i = 1; i <= hours.size(); ++i)
            nums[i] = nums[i - 1] + (hours[i-1] > 8 ? 1 : -1);
        vector<int>stack;
        for (int i = 0; i < nums.size(); ++i) {
            if(stack.empty() || nums[stack.back()] > nums[i])
                stack.push_back(i);
        }
        int ans = 0;
        for (int j = nums.size()-1; j >=0; --j) {
            while (!stack.empty() && nums[stack.back()] < nums[j]) {
                ans = max(ans, j - stack.back());
                stack.pop_back();
            }
        }
        return ans;
    }
};

int main() {
    Solution sol;
    vector<int>hours = { 9,9,6,0,6,6,9 };
    sol.longestWPI(hours);
}